package backtrack;
import java.util.*;
public class _11_46_全排列 {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	// 防止元素重复使用
	boolean[] use;
    public List<List<Integer>> permute(int[] nums) {
    	use = new boolean[nums.length];
    	backtracking(nums);
    	return result;
    }
    
    public void backtracking(int[] nums) {
    	if(item.size() == nums.length) {
    		System.out.println(item);
    		result.add(new ArrayList<>(item));
    		return;
    	}

    	for(int i = 0; i < nums.length; i++) {
    		// 元素未使用过，则新增，并且记录用过，否则跳到下一个元素
    		if(!use[i]) {
    			item.add(nums[i]);
    			use[i] = true;
    		} else {
    			continue;
    		}
    		backtracking(nums);
    		item.remove(item.size() - 1);
    		use[i] = false;
       	}
    	
    }
    
    public static void main(String[] args) {
    	int nums[] = {1,2,3};
		new _11_46_全排列().permute(nums);
	}
}
